class Solution {
    public:
        int maxPossibleScore(vector<int>& start, int d) {
            int n = start.size();
            sort(start.begin(),start.end());
            auto check = [&](int mid){
                int old = start[0];
                for(int i = 1;i < n;i++){
                    if(start[i] + d - old < mid){
                        return false;
                    }
                    old = max(old + mid,start[i]);
                }
                return true;
            };
    
    
            int left = 0,right = (start.back() + d - start[0]) / (start.size() - 1) + 1;
            while(left <= right){
                int mid = left + (right - left)/2;
                if(check(mid)){
                    left = mid + 1;
                }else{
                    right = mid -1;
                }
            }
            return right;
        }
    };
    class Solution {
        public:
            int maximumTastiness(vector<int>& price, int k) {
                ranges::sort(price);
                int n = price.size();
                auto check = [&](int m){
                    int old = price[0] + m,cnt = 1;
                    for(int i = 1;i < n;i++){
                        if(price[i] >= old){
                            cnt++;
                            old = price[i] + m;
                            if(cnt >= k){
                                return true;
                            }
                        }
                    }
                    return false;
                };
                int left = 0,right = price.back();
                while(left <= right){
                    int mid = (left + right) >> 1;
                    if(check(mid)){
                        left = mid + 1;
                    }else{
                        right = mid - 1;
                    }
                }
                return right;
            }
        };
        class Solution {
            public:
                int maxDistance(vector<int>& position, int m) {
                    ranges::sort(position);
                    int n = position.size();
            
                    auto check = [&](int mid){
                        int old = position[0] + mid,cnt = 1;
                        for(int i = 1;i < n;i++){
                            if(old <= position[i]){
                                cnt++;
                                if(cnt >= m){
                                    return true;
                                }
                                old = position[i] + mid;
                            }
                        }
                        return false;
                    };
            
                    int left = 0,right = position.back();
                    while(left <= right){
                        int mid = (left + right) >> 1;
                        if(check(mid)){
                            left = mid + 1;
                        }else{
                            right = mid - 1;
                        }
                    }
                    return right;
                }
            };
            class Solution 
            {
                public:
                    void fun(vector<vector<int>>& grid, vector<vector<int>>& vvi) {
                        stack<pair<int, int>> s1, s2;
                        int n = grid.size();
                        for (int i = 0; i < n; i++)
                            for (int j = 0; j < n; j++)
                                if (grid[i][j] == 1) {
                                    s1.push({i - 1, j});
                                    s1.push({i + 1, j});
                                    s1.push({i, j - 1});
                                    s1.push({i, j + 1});
                                    vvi[i][j] = 0;
                                }
                        int cnt = 1;
                        while (!s1.empty()) {
                            while (!s1.empty()) {
                                auto [x, y] = s1.top();
                                s1.pop();
                                if (x < 0 || y < 0 || x >= n || y >= n || vvi[x][y] != -1)
                                    continue;
                                vvi[x][y] = cnt;
                                s2.push({x - 1, y});
                                s2.push({x + 1, y});
                                s2.push({x, y - 1});
                                s2.push({x, y + 1});
                            }
                            swap(s1, s2);
                            cnt++;
                        }
                    }
                    int maximumSafenessFactor(vector<vector<int>>& grid) {
                        int n = grid.size();
                        vector<vector<int>> vvi(n, vector<int>(n, -1));
                        fun(grid, vvi);
                        vector<vector<bool>> vvb(n, vector<bool>(n, false));
                        auto check = [&](int mid) {
                            for(int i = 0;i < n;i++){
                                for(int j = 0;j < n;j++)
                                    vvb[i][j] = false;
                            }
                            stack<pair<int, int>> s;
                            s.push({0, 0});
                            while (!s.empty()) {
                                auto [x, y] = s.top();
                                s.pop();
                                if (x < 0 || y < 0 || x >= n || y >= n || vvb[x][y])
                                    continue;
                                if (vvi[x][y] < mid)
                                    continue;
                                if (x == n - 1 && y == n - 1)
                                    return true;
                                vvb[x][y] = true;
                                s.push({x - 1, y});
                                s.push({x + 1, y});
                                s.push({x, y - 1});
                                s.push({x, y + 1});
                            }
                            return false;
                        };
                        int left = 0, right =  min(vvi[n - 1][n - 1],vvi[0][0]);
                        while (left <= right) {
                            int mid = (left + right) >> 1;
                            if (check(mid)) {
                                left = mid + 1;
                            } else {
                                right = mid - 1;
                            }
                        }
                        return right;
                    }
                };




class Solution {
    public:
        using ll = long long;
        long long maxPower(vector<int>& stations, int r, int k) {
            int n = stations.size();
            vector<ll> sum(n);
            ll cnt = 0;
            for(int i = 0;i < n + r;i++){
                if(i < n){
                    cnt += stations[i];
                }
                if(i >= r*2 + 1){
                    cnt -= stations[i - r*2 - 1];
                }
                if(i >= r)
                {
                    sum[i - r] = cnt;
                }
            }
            // for(int i = 0;i < n;i++)
            //     cout << sum[i] << ' ';
            // cout << endl;
            int rr =  r*2 + 1;
            auto check = [&](ll m){
                ll cnt1 = 0,cnt2 = 0;
                vector<int> arr(n,0);
                for(int i = 0;i < n;i++){
                    cnt1 -= arr[i];
                    ll tmp =m - sum[i] - cnt1;
                    if(tmp > 0){
                        cnt2 += tmp;
                        cnt1 += tmp;
                        if(cnt2 > k) return false;
                        if(rr + i< n)  arr[rr + i] += tmp;
                    }
                }
                return true;
            };
    
    
    
            ll left = 0,right = *max_element(sum.begin(),sum.end()) + k;
            while(left <= right){
                ll mid = (left + right) >> 1;
                // cout << left <<" " << right << endl;
                if(check(mid)){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
            return right;
        }
    };


class Solution {
    public:
        using ll = long long;
        long long maxScore(vector<int>& points, int m) {
            int n = points.size();
            ll left = 1,
               right = (ll)*max_element(points.begin(), points.end()) * (ll)(m / n);
            vector<ll> g(n);
            auto check = [&](ll mid) {
                ll cnt = 0;
                for (int i = 0; i < n; i++) {
                    g[i] = (mid) / points[i] + (mid % points[i] != 0);
                    cnt += g[i];
                    if (cnt > m) {
                        //  cout << endl;
                        return false;
                    }
                    // cout << g[i] <<' ';
                }
                // cout << endl;
                cnt = 0;
                for (int i = 1; i < n; i++) {
                    cnt += max(2 * g[i - 1] - 1, (ll)1);
                    g[i] -= max((ll)0,g[i - 1] - 1);
                    // cout << g[i] <<' ' <<cnt << '|' ;
                    if(cnt > m){
                        return false;
                    }
                }
                // cout << endl;
                cnt += max(2 * g[n - 1] - 1, (ll)0);
                return cnt <= m;
            };
            while (left <= right) {
                // cout << left << ' ' << right << endl;
                ll mid = (left + right) >> 1;
                if (check(mid)) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return right;
        }
    };